#include "DynamicArray.h"

 DynamicArray::DynamicArray(void(*free)(ElementType)):size(0),capacity(15)
 {
    a = new ElementType[capacity];
    this->free = free;
    this->Compare = nullptr;
 }

 DynamicArray:: ~DynamicArray()
 {  
    if(free != nullptr)
    {
      for(int i = 0;i < size;i++)
         this->free(a[i]);
    }
    delete []a;
 }
 
 DynamicArray::DynamicArray(const DynamicArray& d)
 {
    this->size = d.size;
    this->capacity = d.capacity;
    this->a = new ElementType[this->capacity];
    for(int i = 0; i < this->size;i++)
    {
        a[i] = d.a[i];
    }
 }

 DynamicArray& DynamicArray::operator=(const DynamicArray&d)
 {  
    delete []a;
    this->size = d.size;
    this->capacity = d.capacity;
    this->a = new ElementType[this->capacity];
    for(int i = 0; i < this->size;i++)
    {
        a[i] = d.a[i];
    }
    return *this;
 }

 void DynamicArray::show(void (*func)(ElementType))
 {
      for(int i = 0;i < size;i++)
      {
         func(a[i]);
      }
 }

 void DynamicArray::Resize(int newCapacity)
 {
    this->size = size > newCapacity ? newCapacity : size;
    this->capacity=newCapacity;
    ElementType *newp = new ElementType[newCapacity];
    for(int i = 0; i < size;i++)
    {
        newp[i] = a[i];
    }
    delete []a;
    a = newp;
 }

 void DynamicArray::InsertTail(ElementType element)
 {  
    if(size >= capacity)
        Resize(capacity*2);
    this->a[size++] = element;
 }

 void DynamicArray::InsertHead(ElementType element)
 {
      if(size >= capacity)
        Resize(capacity*2);
      for(int i = this->size;i >= 1;i--)
      {
         a[i] = a[i-1];
      }
      a[0] = element;
      size++;  
 }

 void DynamicArray::InsertByIndex(ElementType element, int index)
 {
      if(index < 0 || index > size)
      {
         std::cout<<"invalid index"<<std::endl;
         return;
      }
      if(size >= capacity)
        Resize(capacity*2);
      for(int i = size; i>=index;i--)
      {
         a[i] = a[i-1];
      }
      a[index] = element;
      size++;
 }

 void DynamicArray::RemoveByIndex(int index)
 {
      for(int i = index; i < size - 1;i++)
      {
         a[i] = a[i+1];
      }
      size--;
 }

 void DynamicArray::RemoveByElement(ElementType element,bool(*isEqual)(ElementType,ElementType))
 {
      for(int i = 0;i < size; i++)
      {
         if(isEqual(a[i],element))
         {  
            this->free(a[i]); //有点搞不懂
            RemoveByIndex(i);
            i--;
         }
      }
 }

 void DynamicArray::UpDataByIndex(int index, ElementType newElement)
 {
       if(index < 0 || index > size)
      {
         std::cout<<"invalid index"<<std::endl;
         return;
      }
      a[index] = newElement;
 }

 void DynamicArray::UpDataByElement(ElementType oldValue, ElementType newValue)
 {
      for(int i = 0;i < size; i++)
      {
         if(a[i] == oldValue)
            a[i] = newValue;
      }
 }

 ElementType &DynamicArray::operator[](int index)
 {
      return a[index];
 }

 DynamicArray DynamicArray::FindByElement(ElementType element)
 {   
     DynamicArray result(nullptr);
     for(int i = 0; i < size; i++)
     {
      if(a[i] == element)
      {
         result.InsertTail((void*)i);
      }
     }
     return result;
 }

 void DynamicArray::SetSortCallBack(bool (*Compare)(ElementType, ElementType))
 {
      this->Compare = Compare;
 }

 void DynamicArray::Sort()
 {    
      if(Compare == nullptr)
      {  
         std::cout<<"排序比较器为空!\n";
         return;
      }
      Sort(0,size-1);
 }

 int DynamicArray::BinarySearch(ElementType element)
 {    
      Sort();
      int left = 0;
      int right = size -1;
      while(left <= right)
      {
         int mid = (left&right)+((left^right)>>1);
         if(a[mid] == element)
            return mid;
         else if(a[mid] > element)
            right = mid -1;
         else if(a[mid] < element)
            left = mid + 1;
      }
      return -1;
 }

 void DynamicArray::Deduplicate()
 {
      Sort();
      for(int i = 1;i < size;i++)
         if(a[i] == a[i-1])
            RemoveByIndex(i--);
 }
//归并排序:合并已经有序的两个数列
 DynamicArray DynamicArray::Merge(const DynamicArray &d)
 {   
     DynamicArray result(nullptr);
     int i = 0,j=0;
     while(i < this->size&&j < d.size)//谁小加谁
     {
         if(a[i] < d.a[j])
         {
            result.InsertTail(a[i++]);
         }
         else
         {
            result.InsertTail(d.a[j++]);
         }
     }

     while(i < this->size)
      result.InsertTail(a[i++]);
     while(j < d.size)
      result.InsertTail(d.a[j++]);
     return result;
 }

 void DynamicArray::Sort(int start, int end)
 {    
      if(start >= end)
         return;
      int left = start;
      int right = end;
      ElementType temp = a[left];
      while(left < right)
      {
         while(left < right&&Compare(a[right],temp))
            right--;
         if(left < right)
            a[left++] = a[right];
         while(left < right&&Compare(temp,a[left]))
            left++;
         if(left < right)
            a[right--] = a[left];
      }
      a[left] = temp;
      Sort(start,left-1);
      Sort(right+1,end);
 }

 std::ostream &operator<<(std::ostream &os, const DynamicArray &d)
 {
   //   os<<"size:"<<d.size<<"capacity:"<<d.capacity<<std::endl;
   //   for(int i = 0;i < d.size;i++)
   //   {
   //       os<<d.a[i]<<" ";
   //   }
   //   os<<std::endl;
   //   return os;
 }
